﻿using System;
using System.Collections.Generic;

namespace ConsoleApp_DFS
{
    class Program
    {
        /*
         * 
         输入 3 得到下面列表
         [
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
        有效括号组合
         */

        static void Main(string[] args)
        {
            //Console.WriteLine("请输入括号的对数：");
            //if (int.TryParse(Console.ReadLine(), out int userInput) && userInput > 0)
            //{
            //    List<string> result = new List<string>();
            //    CombinationBracket(userInput, userInput, "", result);
            //    Console.WriteLine($"userInput {userInput}, Get Result :");
            //    result.ForEach(ret => Console.WriteLine(ret));
            //}
            //else
            //{
            //    Console.WriteLine("用户输入参数错误！");
            //}

            List<string[]> ls = new List<string[]> ();
            string[] arrStr = { "a", "b", "c" };
            //CombinationSort( ls, arrStr,0, arrStr.Length-1);
            int[] tempInt = new int[2];
            GetCombination(ref ls, arrStr, arrStr.Length, 2, tempInt, 2);
            ls.Clear();
            ls = GetCombinationSort(arrStr, 2);
            Console.ReadLine();
        }

        static void CombinationBracket(int left, int right, string str, List<string> resultLs)
        {
            if (left == 0 && right == 0)
            {
                resultLs.Add(str);
                return;
            }

            if (left > 0)
            {
                CombinationBracket(left - 1, right, str + "(", resultLs);
            }
            if (right > 0 && right > left)
            {
                CombinationBracket(left, right - 1, str + ")", resultLs);
            }

        }

        static void CombinationSort<T>( List<T[]> ls, T[] arr ,int s,int e)
        {
            if (s>e)
            {
                return;
            }else if(s==e){
                T[] tempArr = new T[arr.Length];
                arr.CopyTo(tempArr, 0);
                ls.Add(tempArr);
                return;
            }
            for (int i = s; i <=e ; i++)
            {
                T temp = arr[i];
                arr[i] = arr[s];
                arr[s] = temp;
                CombinationSort( ls, arr,s+1, e);
                 temp = arr[i];
                arr[i] = arr[s];
                arr[s] = temp;
            }

        }

        static void SortStandAnswer<T>(ref List<T[]> resultLs, T[] arr,int startIndex,int endIndex)
        {
            if (startIndex == endIndex )
            {
                if (resultLs==null)
                {
                    resultLs = new List<T[]>();
                }
                T[] retArr = new T[arr.Length];
                arr.CopyTo(retArr, 0);
                resultLs.Add(retArr);
            }
            else
            {
                //进行排序
                SwapVal(ref arr[startIndex], ref arr[endIndex]);
                SortStandAnswer(ref resultLs, arr, startIndex + 1, endIndex);
                SwapVal(ref arr[startIndex], ref arr[endIndex]);
            }
        }

        static void SwapVal<T>(ref T t1,ref T t2)
        {
            T temp = t1;
            t1 = t2;
            t2 = temp;
        }

        /// <summary>
        /// 组合
        /// </summary>
        /// <typeparam name="T">要组合数据类型</typeparam>
        /// <param name="resultLs">结果集合</param>
        /// <param name="arr">源集合</param>
        /// <param name="n">源集合长度</param>
        /// <param name="m">挑出元素个数</param>
        /// <param name="b">调出元素个数数组</param>
        /// <param name="M">固定，挑出元素个数</param>
        static void GetCombination<T>(ref List<T[]> resultLs,T[] arr,int n,int m ,int[] b,int M)
        {
            for (int i = n; i >= m; i--)
            {
                b[m - 1] = i - 1;
                if (m>1)
                {
                    GetCombination(ref resultLs, arr, i - 1, m - 1, b, M);
                }
                else
                {
                    if (resultLs == null)
                    {
                        resultLs = new List<T[]>();
                    }
                    T[] temp = new T[M];
                    for (int j = 0; j < b.Length; j++)
                    {
                        temp[j] = arr[b[j]];
                    }
                    resultLs.Add(temp);
                }
            }
        }

        /// <summary>
        /// 从arr中调出m进行排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="m"></param>
        /// <returns></returns>
        static List<T[]> GetCombinationSort<T>(T[] arr,int m)
        {
            if (arr == null||m>arr.Length)
            {
                return null;
            }
            List<T[]> resList = new List<T[]>();
            //先组合
            int[] tempInt = new int[m];
            List<T[]> c=null;
           GetCombination(ref c, arr, arr.Length,m,tempInt,m);
            for (int i = 0; i < c.Count; i++)
            {
                List<T[]> ts = new List<T[]>();
                //数组全排序
                CombinationSort(ts, c[i], 0, c[i].Length - 1);
                resList.AddRange(ts);
            }
            return resList;
        }

        //二分法查找
        static int BinarySearch(int[] arr,int low ,int high,int target)
        {
            if (low>high)
            {
                return -1;
            }
            int mid = (low + high) / 2;
            if (arr[mid]>target )
            {
                return BinarySearch(arr, low, mid - 1, target);
            }else if (arr[mid]<target)
            {
                return BinarySearch(arr, mid + 1, high, target);
            }
            else
            {
                return mid;
            }
        }
    }
}
